package com.guaoran.algorithm.binary.tree;

import com.guaoran.algorithm.common.CommonUtil;
import com.guaoran.algorithm.entity.TreeNode;

/**
 * @author : 孤傲然
 * @description : 二叉平衡树
 * https://leetcode.com/problems/balanced-binary-tree/
 * @date :2021/1/21 22:35
 */
public class BalancedBinaryTree {
    public static void main(String[] args) {
        TreeNode treeNode = CommonUtil.createTreeNode(new Integer[]{3, 9, 20, null, null, 15, 7});
        System.out.println(CommonUtil.readTreeNode(treeNode));
        System.out.println(isBalanced(treeNode));
        System.out.println(isBalanced(CommonUtil.createTreeNode(new Integer[]{1,2,2,3,3,null,null,4,4})));
        System.out.println(isBalanced(CommonUtil.createTreeNode(new Integer[]{1,2,null,3,null,4,null,5})));
    }
    public static boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }

        return maxSize(root) != -1;
    }

    private static int maxSize(TreeNode root) {
        if(root == null){
            return 0;
        }
        int left = maxSize(root.left);
        int right = maxSize(root.right);
        if(left == -1 || right == -1 ||  Math.abs(left - right) > 1){
            return -1;
        }
        return Math.max(left,right) + 1;
    }
}
